package frist50;

import java.util.*;

public class T0022 {
    public List<String> generateParenthesis(int n) {
        Deque<StringBuffer> deque = new LinkedList<>();
        deque.add(new StringBuffer("()"));
        if (n == 1) return new LinkedList<String>(){{add("()");}};
        for (int i = 1; i < n; i++) {
            int size = deque.size();
            for (int j = 0; j < size; j++) {
                StringBuffer str=new StringBuffer(deque.peek()) ;
                int strlen=str.length();
                for (int k = 0; k <strlen ; k++) {
                    char c=str.charAt(k);
                    if (c=='('){
                        str.insert(k+1,'(');
                        str.insert(k+2,')');
                        deque.add(str);
                        str=new StringBuffer(deque.peek()) ;
                    }
                }
                deque.add(new StringBuffer(deque.poll().append("()")));
            }
        }
        List<String> re=new ArrayList<>();
        int size=deque.size();
        Set<String> hashSet=new HashSet<>();
        for (int i = 0; i <size ; i++) {
            String str=deque.poll().toString();
            if(!hashSet.contains(str)){
                re.add(str);
                hashSet.add(str);
            }
        }
        return re;
    }
}
